/****************************************************************************
 * Elisa 1.0                                                                *
 *--------------------------------------------------------------------------*
 * Author: Laurent Granvilliers, Vincent Sorin                              *
 * Copyright (c) 2004 Laboratoire d'Informatique de Nantes Atlantique       *
 *--------------------------------------------------------------------------*
 * Elisa is distributed WITHOUT ANY WARRANTY. Read the associated           *
 * COPYRIGHT file for more details.                                         *
 *--------------------------------------------------------------------------*
 * elisa_search_strategy.h                                                  *
 ****************************************************************************/

/**
 * @file elisa_search_strategy.h
 * @brief Classes for search strategies
 */


#ifndef _ELISA_SEARCH_STRATEGY_H
#define _ELISA_SEARCH_STRATEGY_H

#include <map>
#include <memory>
#include "elisa_defs.h"
#include "elisa_variable.h"

NAMESPACE_ELISA
/**
 * @ingroup Variable
 * @class VariableSet
 * @brief class used to store VariableImpls of the same priority
 */
class VariableSet : public VarImplSet
{
public:

	/**
 	 * @brief Constructor
 	 * @param p the priority of the VariableImpl stored
 	 */
	VariableSet(int p = 0)
		: VarImplSet(), m_priority(p)
	{
	}

	/**
 	 * @brief Destructor
 	 */
	~VariableSet()
	{
	}

	/**
 	 * Returns the priority of the VariableImplementation stored
 	 * @return the priority of the set
 	 */
	int getPriority() const
	{
		return m_priority;
	}

	/**
 	 * Inserts a VariableImplementation in the set
 	 * @param v the VariableImplementation to store
 	 * @pre v->getPriority() == this->getPriority()
 	 */

	void insert(VarImplPtr v)
	{
		VarImplSet::insert(v);
	}

	/**
 	 * Returns true when the search over the domain of v can be ended.
 	 * Default implementation: the domain of v domain is not splittable
 	 * @return true if the VariableImpl is a solution
 	 */
	virtual bool isSolution(const VariableImpl & v) const
	{
		return !(v.isSplittable());
	}

	/**
 	 * @brief returns the best splittable variable
 	 * @return a pointer to a VariableImplementation, or NULL if no variables are splittable
 	 */
	VarImplPtr getBest()
	{
		//SetVar::iterator imv;
		VarImplSet::const_iterator imv;
		VarImplPtr result;

		for (imv = begin(); imv != end(); ++imv) {
			if (result.get() == NULL) {
				if (!(this->isSolution(**imv))) {
					result = *imv;
				}
			} else {
				if (((*imv)->best(result)) && !(this->isSolution(**imv))) {
					result = *imv;
				}
			}
		}
		return result;
	}

	/*
 	   /// @name iterator through the set
 	   //@{
 	   SetVar::const_iterator beginVar()
 	   {
 	   return _s.begin();
 	   }

 	   SetVar::const_iterator endVar()
 	   {
 	   return _s.end();
 	   }
 	   //@}
 	 */

private:
	// @var set where VariableImplementation are stored
	//SetVar _s;

	// @var priority of the set
	int m_priority;
};


/**
 * @class ltInt
 * @brief class for int comparison
 */
struct ltInt 
{
	bool operator()(const int i1, const int i2) const
	{
		return(i1 < i2);
	}
};

typedef boost::shared_ptr<VariableSet> VariableSetPtr;

/**
 * @ingroup Variable
 * @class VariableSetMap
 * @brief map of VariableSets using the STL map
 */
typedef std::map<int, VariableSetPtr, ltInt> VariableSetMap;


class ChoiceStrategy;

typedef std::auto_ptr<ChoiceStrategy> ChoiceStrategyPtr;
//typedef ChoiceStrategy *ChoiceStrategyPtr;


/**
 * @ingroup Search
 * @class SplitChooser
 * @brief Base class for variable choice during search
 */
class SplitChooser
{
public:
	/// Exception class
	class NoSplitableVar { };

	/**
 	 * Constructor used by elisa
 	 * @post Strategy is defined
 	 */
	SplitChooser(ChoiceStrategy *s);

	/**
 	 * Destructor
 	 * @post all SetVariables have been deleted
 	 */
	virtual ~SplitChooser ();

	/**
 	 * @brief insert a VariableImplementation in the SplitChooser
 	 * @param v the VariableImplementation to add
 	 */
	virtual void insert(VarImplPtr v);

	/**
 	 * @Choice strategy
 	 * @param s the Stategy to change
 	 */
	void setChoiceStrategy(ChoiceStrategy *s);

	/**
 	 * Returns true when the search over the domain of v can be ended.
 	 * Default implementation: the domain of v domain is not splitable
 	 */
	bool isSolution(const VariableImpl & v) const;

	/**
 	 * Returns true if the current box is a solution.
 	 * Default implementation: the current box is not splitable
 	 */
	bool isSolution();

	/**
 	 * @brief Choice function:
 	 * msol is used to determine which variable can be chosen
 	 */
	VarImplPtr get() throw (SplitChooser::NoSplitableVar);

	/**
 	 * Return the SetVar Sv
 	 */
	VariableSet *getVariables();

	/**
 	 * Return the SetVar Sv of the priority
 	 */
	VariableSet *getVariables(int priority);

	/**
 	 * Return the MaxPriority
 	 */
	int getMaxPriority() const;

private:
	// @var Set of variables
	VariableSet m_varSet;

	// @var Map of variables' set
	VariableSetMap m_varSetMap;

	// @var current ChoiceStrategy
	ChoiceStrategyPtr m_strategy;

	// @var Priority of the first variable
	int m_maxPriority;

protected:
	// @var SplitChooser using the strategy
	//SplitChooser *m_sc;
};

//typedef SplitChooser *SplitChooserPtr;
typedef boost::shared_ptr<SplitChooser> SplitChooserPtr;


/**
 * @ingroup Search
 * @class ChoiceStrategy
 * @brief
 */
class ChoiceStrategy
{
public:
	/**
 	 * Default Constructor
 	 */
	ChoiceStrategy(SplitChooser *s = 0)
		: m_chooser(s)
	{
	}

	/**
 	 * Destructor
 	 */
	~ChoiceStrategy()
	{
	}

	/**
 	 * Setter parent
 	 */
	void setChooser(SplitChooser *chooser)
	{
		m_chooser = chooser;
	}

	/**
 	 * Choice function
 	 * @return the VarImp next after the last chosen VariableImplementation
 	 */
	virtual VarImplPtr get() throw (SplitChooser::NoSplitableVar) = 0;

protected:
	// @var SplitChooser using the strategy
	SplitChooser *m_chooser;
};


/**
 * @ingroup Search
 * @class SearchRoundRobin
 * @brief Choice of a variable w.r.t. the round-robin strategy
 */
class SearchRoundRobin : public ChoiceStrategy
{
public:

	/**
 	 * Constructor
 	 */
	SearchRoundRobin(SplitChooser *s = 0);

	/**
 	 * Destructor
 	 */
	~SearchRoundRobin();

	/**
 	 * Choice function
 	 * @return the VariableImplementation next after the last chosen VariableImplementation
 	 */
	VarImplPtr get() throw (SplitChooser::NoSplitableVar);

	/**
 	 * Return the last chosen variable
 	 */
	VarImplPtr getLastVar();

private:
	// @var last chosen variable
	VarImplPtr m_var;

	// @var the corresponding iterator in the model
	VarImplSet::const_iterator m_it;
};


/**
 * @ingroup Search
 * @class SearchMaxInterval
 * @brief Choice of the variable of largest domain during search
 */
class SearchMaxInterval : public ChoiceStrategy
{
public:
	/// Constructor
	SearchMaxInterval(SplitChooser *s = 0);

	/// Destructor
	~SearchMaxInterval();

	/**
 	 * Choice function
 	 * @return a pointer to the best VariableImplementation for splitting
 	 */
	VarImplPtr get() throw (SplitChooser::NoSplitableVar);
};

END_NAMESPACE_ELISA

#endif // ELISA_SEARCH_STRATEGY
